package com.laoyao.service;


import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

import com.laoyao.util.WordUtil;
 
/**
 * created by jiayaoguang at 2017年9月28日 敏感词过滤
 */
public class WordService {
 
	private final TrieNode root;
 
	public static void main(String[] args) {
 
		String[] keywords = new String[] { "人能世界那1大那大好人坏人1", "世界那1大那大好人坏人1", "能世界那1大那大好人坏人1", "界那1大那大好人坏人1",
				"那1大那大好人坏人1", "1大那大好人坏人", "坏1人", "世界那大", "世界那么大","你大爷" };
		//String[] keywords = new String[] { "shee","he" };
		WordService find = new WordService(keywords);
		String text = find.wordPass("hah人你大爷人人,你大爷");
		//int index = find.find("shedeeshee");
		
		System.out.println(text);
 
	}
 
	public WordService(String[] keywords) {
		root = buildTree(keywords);
		 printTree(root);
		addFailNode(root);
	}
 
	/**
	 * 查找是否包含目标字符串
	 */
	public int find(String text) {
		int len = text.length();
		int start =0;
		TrieNode node = root;
 
		for (int index = 0; index < len; index++) {
			char c = text.charAt(index);
				
 
			while (node != null && node.getSonNode(c) == null) {
				//System.out.println(node.getFailNode());
				node = node.getFailNode();
			}
			
 
			node = (node == null ? root : node.getSonNode(c));
 
			TrieNode temp = node;
 
			while (temp != null) {
				if (temp.isWordEnd()) {
					start=index-temp.getLength()+1;
					System.out.println(start+"--"+index);
					text=WordUtil.replaceWord(text, start, index);
					System.out.println(text);
					//return index;
				}
				temp = temp.getFailNode();
			}
		}
		return -1;
	}
	
	/**
	 * 过滤敏感词
	 */
	public String wordPass(String text){
		int len = text.length();
		int start =0;
		TrieNode node = root;
 
		for (int index = 0; index < len; index++) {
			char c = text.charAt(index);
				
 
			while (node != null && node.getSonNode(c) == null) {
				//System.out.println(node.getFailNode());
				node = node.getFailNode();
			}
			
 
			node = (node == null ? root : node.getSonNode(c));
 
			TrieNode temp = node;
 
			while (temp != null) {
				if (temp.isWordEnd()) {
					start=index-temp.getLength()+1;
					System.out.println(start+"--"+index);
					text=WordUtil.replaceWord(text, start, index);
					System.out.println(text);
					//return index;
				}
				temp = temp.getFailNode();
			}
		}
		return text;
	}
 
	/**
	 * 初始化字典树
	 */
	private TrieNode buildTree(String[] keywords) {
		final TrieNode root = new TrieNode(' ');
		for (String word : keywords) {
			TrieNode temp = root;
			for (char ch : word.toCharArray()) {
				if (temp.containsSonNode(ch)) {
					temp = temp.getSonNode(ch);//如果包含了，temp就往子节点移动
				} else {
					TrieNode newNode = new TrieNode(ch);
					temp.addSonNode(newNode);
					temp = newNode;
				}
			}
			temp.setWordEnd(true);
			temp.setLength(word.length());
		}
		return root;
	}
 
	/**
	 * 添加节点
	 */
	private void addWordToTree(TrieNode rootNode, String word) {
		if (word == null || word.length() == 0) {
			return;
		}
		for (char c : word.toCharArray()) {
			if (rootNode.containsSonNode(c)) {
				rootNode = rootNode.getSonNode(c);
			} else {
				TrieNode newNode = new TrieNode(c);
				rootNode.addSonNode(newNode);
				rootNode = newNode;
			}
		}
		rootNode.setWordEnd(true);
	}
 
	public void printTree(TrieNode root) {
		Queue<TrieNode> queue = new LinkedList<TrieNode>();
		queue.offer(root);
		TrieNode enterNode = new TrieNode('\n');
		queue.add(enterNode);
		while (!queue.isEmpty()) {
			TrieNode parent = queue.poll();
			System.out.print(parent.getValue() + ";");
			if (parent == enterNode && queue.size() > 1) {
				queue.offer(enterNode);
				continue;
			}
			queue.addAll(parent.getSonsNode());
		}
 
	}
 
	/**
	 * BFS遍历树，给每一个节点建立FailNode
	 */
	private void addFailNode(final TrieNode root) {
		root.setFailNode(null);
		Queue<TrieNode> queue = new LinkedList<TrieNode>();
		queue.add(root);
		while (!queue.isEmpty()) {
			TrieNode parent = queue.poll();
			TrieNode temp;
			for (TrieNode child : parent.getSonsNode()){
				if (parent == root) {
					child.setFailNode(root);
				} else {
					temp = parent.getFailNode();
					while (temp != null) {
 
						TrieNode node = temp.getSonNode(child.getValue());
						if (node != null) {
							child.setFailNode(node);
							break;
						}
						temp = temp.getFailNode();
					}
					if (temp == null) {
						child.setFailNode(root);
					}
				}
				queue.add(child);
			}
		}
	}
 
	
}